Note--Sequencing with Finite Intermediate Storage

摘要

This note presents procedures for finding optimal solutions to the deterministic N-job two machine flow-shop sequencing problem when the buffer size z is nearly the same as the number of jobs. When m = N - z - 2 is small, a simple and fast procedure that uses Johnson's algorithm on the middle N - 2m jobs is used. The procedure has a computational complexity of o(N 2m+1 ) comparisons.